package advanced.class05;

import java.util.LinkedList;
import java.util.List;

/**
 * 左神算法进阶版————第五课
 * 题目描述：
 * 		给定一个二维数组，每个元素索引表示当前员工代号。
 * 		数据中第一个元素表示当前位置元素的直系领导
 * 		数据中第二个元素表示此员工的活跃度
 * 		公司组织年会，请你求出最大的活跃值
 */
public class Code_04_MaxHappy {

	public static class Node{
		int huo;
		List<Node> nexts;

		public Node(int huo){
			this.huo = huo;
			nexts = new LinkedList<>();
		}
	}

	public static int getMaxHuo(Node root){
		if(root == null) return 0;
		ResultData res = action(root);
		return Math.max(res.bu_lai_huo,res.lai_huo);
	}

	private static ResultData action(Node root) {
		int lai_huo = root.huo;
		int bu_lai_huo = 0;

		for (int i = 0; i < root.nexts.size(); i++) {
			Node node = root.nexts.get(i);
			ResultData cur = action(node);
			lai_huo += cur.bu_lai_huo;
			bu_lai_huo += Math.max(cur.bu_lai_huo,cur.lai_huo);
		}

		return new ResultData(lai_huo,bu_lai_huo);
	}

	public static class ResultData{
		int lai_huo;
		int bu_lai_huo;

		public ResultData(int lai_huo, int bu_lai_huo){
			this.lai_huo = lai_huo;
			this.bu_lai_huo = bu_lai_huo;
		}
	}

	// 数据DP求解
	public static int maxHappy(int[][] matrix) {
		int[][] dp = new int[matrix.length][2];  // 创建辅助数组（dp[i][0]表示第i员工不来的时候的活跃度，dp[i][1]表示第i个员工来的时候的活跃度）
		boolean[] visited = new boolean[matrix.length];  // 创建标志数组。表示该员工有没有到访
		int root = 0;
		for (int i = 0; i < matrix.length; i++) {
			if (i == matrix[i][0]) {
				root = i;
			}
		}
		// 找出最大的boss，就是根节点
		// 带入计算
		process(matrix, dp, visited, root);
		return Math.max(dp[root][0], dp[root][1]);
	}

	public static void process(int[][] matrix, int[][] dp, boolean[] visited, int root) {
		visited[root] = true;      // 首先计算出root位置的员工来的时候的活跃度
		dp[root][1] = matrix[root][1];
		for (int i = 0; i < matrix.length; i++) {
			// 遍历数组中所有的员工， 找出当前节点的直接下属（如果当前员工没有被访问过）
			if (matrix[i][0] == root && !visited[i]) {
				process(matrix, dp, visited, i);  // 递归进入下级员工
				dp[root][1] += dp[i][0];          // 当前员工来的时候的活跃度
				dp[root][0] += Math.max(dp[i][1], dp[i][0]);     // 当前员工不来的时候的活跃度
			}
		}
	}

	public static void main(String[] args) {
		int[][] matrix = { { 1, 8 }, { 1, 9 }, { 1, 10 } };
		System.out.println(maxHappy(matrix));
	}
}
